package chapter03_binaryTree;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 描述：
 *      通过先序和中序数组生成后序数组
 *      流程：先根据先序和中序数组设置后序数组中最右边的值，然后划分出左右子树的先序和后序数组，
 *      先根据右子树划分确定后序数组，然后再试左子树划分。从右到左设置好后序数组
 *
 * @author hl
 * @date 2021/6/2 11:42
 */
public class GetPostArray {
    public static void main(String[] args) {
        GetPostArray getPostArray = new GetPostArray();
        int[] pre = {1,2,4,5,3,6,7};
        int[] in = {4,2,5,1,6,3,7};
        int[] postArray = getPostArray.getPostArray(pre, in);
        System.out.println(Arrays.toString(postArray));
    }

    public int[] getPostArray(int[] pre, int[] in){
        int n = pre.length;
        int[] pos = new int[n];
        HashMap<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            inMap.put(in[i], i);
        }
        posOrder(pre, 0, pre.length - 1, in, 0, in.length - 1, pos, n - 1, inMap);
        return pos;
    }
    private int posOrder(int[] pre, int pi, int pj, int[] n, int ni, int nj, int[] pos, int si, HashMap<Integer, Integer> inMap) {
        if (pi > pj) {
            return si;
        }
        pos[si--] = pre[pi];
        int i = inMap.get(pre[pi]);
        si = posOrder(pre, pi + i - ni + 1, pj, n, i + 1, nj, pos, si, inMap);
        return posOrder(pre, pi + 1, pi + i - ni, n, ni, i - 1, pos, si, inMap);
    }


}
